struct Aho{

enum{ALPHA_SIZE=26}; // 字母种类

vector<array<int, ALPHA_SIZE>> Trie;
vector<int> Flag; // 记录末端对应的索引
vector<int> Fail; 
vector<vector<int>> G; // Fail树

array<int, 256> L2I;

void init(int capa=1E6){
    for(int i=0;i<ALPHA_SIZE;++i){
        L2I[i + 'a'] = i;
    }

    Trie.reserve(capa);
    Fail.reserve(capa);
    Flag.reserve(capa);
    G.reserve(capa);
    
    SCnt = 0;
    ErrorState = _newState();
    StartState = _newState();

    return;
}

template<typename IT=string::iterator>
void insert(IT s, IT e, int idx){
    int state = StartState;
    for(auto it=s;it!=e;++it){
        int sn = L2I[(int)*it];
        if(0 == Trie[state][sn]){
            Trie[state][sn] = _newState();
        }
        state = Trie[state][sn];
    }
    Flag[state] = idx;
    return;
}

void buildAC(){
    Fail[StartState] = StartState;
    queue<int> q;
    for(int i=0;i<ALPHA_SIZE;++i){
        int & state = Trie[StartState][i];
        if(state){
            Fail[state] = StartState;
            q.push(state);
            G[StartState].push_back(state);
        }else{
            state = StartState;
        }
    }

    while(not q.empty()){
        int u = q.front(); q.pop();
        for(int i=0;i<ALPHA_SIZE;++i){
            int & state = Trie[u][i];
            if(state){
                Fail[state] = Trie[Fail[u]][i];
                q.push(state);
                G[Trie[Fail[u]][i]].push_back(state);
            }else{
                state = Trie[Fail[u]][i];
            }
        }
    }

    return;
}

template<typename IT = string::iterator>
void query(IT s, IT e, std::function<void(int, int)> f){
    int state = StartState;
    for(auto it=s;it!=e;++it){
        int sn = L2I[(int)*it];
        state = Trie[state][sn];
        f(state, Flag[state]);        
    }
    return;
}

int _newState(){
    Trie.push_back({0});
    Fail.push_back(0);
    Flag.push_back({});
    G.push_back({});
    return SCnt++;
}

int StartState;
int ErrorState;
int SCnt;

};